﻿#define _CRT_SECURE_NO_WARNINGS 1

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;


// 输入一个递增排序的数组和一个数字s，
// 在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        // 利用单调性，使用双指针解决
        sort(nums.begin(), nums.end());
        int left = 0, right = nums.size() - 1;
        while (left < right)
        {
            int sum = nums[left] + nums[right];
            // 比target大，那么left后面的加right的也比target大，所以right--
            if (sum > target)
                right--;
            // 比target小，那么right前面的加left的也比target小，所以left++
            else if (sum < target)
                left++;
            else
                return { nums[left],nums[right] };
        }
        // 照顾编译器
        return { -1,-1 };
    }
};

// 给你一个整数数组 nums ，判断是否存在三元组[nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，
// 同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

// 你返回所有和为 0 且不重复的三元组。

// 先排序
// 然后固定⼀个数 a
// 在这个数后⾯的区间内，使⽤「双指针算法」快速找到两个数之和等于 -a 即可
// 找到⼀个结果之后， left 和 right 指针要跳过重复的元素
// 当使⽤完⼀次双指针算法之后，固定的 a 也要跳过重复 的元素
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> ret;
        for (size_t i = 0; i < nums.size(); ++i)
        {
            // 第一个数去重
            if (i >= 1 && nums[i] == nums[i - 1])
                continue;
            int left = i + 1, right = nums.size() - 1;
            while (left < right)
            {
                int sum = nums[left] + nums[right];
                if (sum < -nums[i])
                    left++;
                else if (sum > -nums[i])
                    right--;
                else
                {
                    ret.push_back({ nums[i],nums[left++],nums[right--] });
                    // 去重
                    while (left < right && nums[left] == nums[left - 1])
                        left++;
                    while (left < right && nums[right] == nums[right + 1])
                        right--;
                }

            }
        }

        return ret;
    }
};

class Solution
{
public:
    vector<vector<int>> threeSum(vector<int>& nums)
    {
        vector<vector<int>> ret;
        // 1. 排序
        sort(nums.begin(), nums.end());
        // 2. 利⽤双指针解决问题
        int n = nums.size();
        for (int i = 0; i < n; ) // 固定数 a
        {
            if (nums[i] > 0) break; // ⼩优化
            int left = i + 1, right = n - 1, target = -nums[i];
            while (left < right)
            {
                int sum = nums[left] + nums[right];
                if (sum > target) right--;
                else if (sum < target) left++;
                else
                {
                    ret.push_back({ nums[i], nums[left], nums[right] });
                    left++, right--;
                    // 去重操作 left 和 right
                    while (left < right && nums[left] == nums[left - 1]) left++;
                    while (left < right && nums[right] == nums[right + 1])right--;
                }
            }
            // 去重 i 
            i++;
            while (i < n && nums[i] == nums[i - 1]) i++;
        }
        return ret;
    }
};

//给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。
//请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] 
//（若两个四元组元素一一对应，则认为两个四元组重复）：

//0 <= a, b, c, d  < n
//  a、b、c 和 d 互不相同
//   nums[a] + nums[b] + nums[c] + nums[d] == target

// 依次固定⼀个数 a ；
//  b.在这个数 a 的后⾯区间上，利⽤「三数之和」找到三个数，使这三个数的和等于 target- a 即可
class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        //1.排序
        sort(nums.begin(), nums.end());
        vector<vector<int>> ret;
        // 固定一个数a
        for (size_t i = 0; i < nums.size(); i++)
        {
            // 第一个数去重
            if (i >= 1 && nums[i - 1] == nums[i])
                continue;
            // 固定一个数b
            // 使用双指针
            for (size_t j = i + 1; j < nums.size(); j++)
            {
                // 这里注意是j >= i+2不是j >= 2
                // 因为必须是在第二个for循环中去重，i必须相等，j>=2可能存在i在不同的位置
                // 比如 -2 -1 -1 1 1 2 2 
                if (j >= i + 2 && nums[j] == nums[j - 1])
                    continue;
                long long  aim = (long long)target - nums[i] - nums[j];
                int left = j + 1, right = nums.size() - 1;
                while (left < right)
                {
                    int sum = nums[left] + nums[right];
                    if (sum < aim)
                        left++;
                    else if (sum > aim)
                        right--;
                    else
                    {
                        ret.push_back({ nums[i],nums[j],nums[left++],nums[right--] });
                        // left 和right去重
                        while (left < right && nums[left] == nums[left - 1])
                            left++;
                        while (left < right && nums[right] == nums[right + 1])
                            right--;
                    }
                }
            }
        }

        return ret;
    }
};

class Solution
{
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target)
    {
        vector<vector<int>> ret;
        // 1. 排序
        sort(nums.begin(), nums.end());
        // 2. 利⽤双指针解决问题
        int n = nums.size();
        for (int i = 0; i < n; ) // 固定数 a
        {
            // 利⽤ 三数之和
            for (int j = i + 1; j < n; ) // 固定数 b
            {
                // 双指针
                int left = j + 1, right = n - 1;
                long long aim = (long long)target - nums[i] - nums[j];
                while (left < right)
                {
                    int sum = nums[left] + nums[right];
                    if (sum < aim) left++;
                    else if (sum > aim) right--;
                    else
                    {
                        ret.push_back({ nums[i], nums[j], nums[left++],
                       nums[right--] });
                        // 去重⼀
                        while (left < right && nums[left] == nums[left - 1])
                            left++;
                        while (left < right && nums[right] == nums[right + 1])
                            right--;
                    }
                }
                // 去重⼆
                j++;
                while (j < n && nums[j] == nums[j - 1]) j++;
            }
            // 去重三
            i++;
            while (i < n && nums[i] == nums[i - 1]) i++;
        }
        return ret;
    }
};


//给定一个含有 n 个正整数的数组和一个正整数 target 。

//找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl + 1, ..., numsr - 1, numsr] ，
// 并返回其长度。如果不存在符合条件的子数组，返回 0 。

// 滑动窗口
class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int left = 0, right = 0, sum = 0;
        int len = INT_MAX;
        while (right < nums.size())
        {
            sum += nums[right];
            //如何减去最左边的还是大于，则需要继续减
            while (sum >= target)
            {
                len = min(len, right - left + 1);
                sum -= nums[left++];
            }
            right++;
        }
        // 等于最大整形值说明不存在符合的子数组，返回0
        return len == INT_MAX ? 0 : len;
    }
};
int main()
{
	return 0;
}